package com.algrithom.linktable;

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

import com.common.model.ListNode;

/**
 * 142. 环形链表 II
 * 141. 环形链表
 * 
 * @author think
 */
public class Solution4 {
    
    public ListNode<Integer> detectCycle(ListNode<Integer> head){
        ListNode<Integer> pos = head;
        Set<ListNode<Integer>> visited = new HashSet<>();
        while (Objects.nonNull(pos)) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.getNext();
        }
        return null;
    }
    
    public ListNode<Integer> detectCycle2(ListNode<Integer> head){
        ListNode<Integer> fast = head;
        ListNode<Integer> slow = head;
        do {
            if (fast == null || fast.getNext() == null) {
                return null;
            }
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        } while (fast != slow);
        fast = head;
        while (slow != fast) {
            slow = slow.getNext();
            fast = fast.getNext();
        }
        return fast;
    }
    public boolean hasCycle(ListNode<Integer> head) {
        if (Objects.isNull(head) || Objects.isNull(head.getNext())) {
            return false;
        }
        ListNode<Integer> fast = head.getNext();
        ListNode<Integer> slow = head;
        do {
            if (Objects.isNull(fast) || Objects.isNull(fast.getNext())) {
                return false;
            }
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        } while (fast != slow);
        return !Objects.isNull(slow);
    }
}
